package com.roc.learn.goodgoodstudy.algorithms;

/**
 * 快速排序
 * O(n log n)
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] array = {6, 1, 2, 7, 9, 11, 4, 5, 10, 8};
        QuickSort(array, 0, array.length - 1);
        for (int a : array) {
            System.out.print(a + ",");
        }
        System.out.println(",");

    }

    /**
     * 教学
     */

    public static void QuickSort(int[] array, int start, int end) {

        if (start > end) {
            return;
        }
        for (int a : array) {
            System.out.print(a + ",");
        }
        System.out.println(",");
        int pivot, i, j, temp;

        i = start;
        j = end;
        pivot = array[i];
        while (i < j) {
            while (i < j && array[j] >= pivot) j--;
            while (i < j && array[i] <= pivot) i++;
            if (i < j) {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        temp = array[start];
        array[start] = array[i];
        array[i] = temp;

        QuickSort(array, start, j - 1);
        QuickSort(array, j + 1, end);
    }


    /**
     * 练习1

     */


}
